Virtual memory hardware, and software such as operating systems and binary instrumentation frameworks often partition memory into fixed-size chunks called pages. In order to store and retrieve metadata associated with these pages, both hardware and software can use a data structure called the page table. The page size and the exact layout of the page table may or may not be dictated by the hardware and performance considerations.
In the case of 32-bit address spaces and with a typical page size of 4 kilobytes, the number of pages is 1,048,576. Depending on the size of metadata associated with each page, the simplest page table can be implemented as a mere one-dimensional array of 1,048,576 elements of the domain type representing the metadata. For example, if the metadata is 4-bytes in size per page, the total amount of memory taken up by such a trivial one-dimensional page table would be 4 megabytes. The one-dimensional page table is accessed using a page number as an index. The page number is the result of dividing a memory address by the page size.
While the one-dimensional approach may still be viable for 32-bit address spaces, its direct application in larger address spaces, such as a full 64-bit address space, is becoming increasingly unbearable as the width of the address space grows.
The typical page size of 4 kilobytes is still a commonplace with 64-bit address spaces and so there are 4,503,599,627,370,496 4-kilobyte pages in them. If the metadata continues to be 4-bytes in size per page, the total amount of memory taken up by a hypothetical one-dimensional page table would be 16 petabytes, which is clearly beyond practical usability and also beyond the memory capacities found in the contemporary computers.
The one-dimensional approach is therefore not viable for large address spaces. Moreover, it can be wasteful in terms of memory utilization and CPU cycles even in the case of a small 32-bit address space, when only a few pages are used and the rest is never accessed. In that case the portions of the page table that correspond to the unused pages are also unused, but must be allocated and initialized.
Hardware and operating systems have traditionally approached these problems by splitting the page table into 2, 3 or 4 levels of indirection. The drawback of this approach is slower access to the metadata. Where the one-dimensional approach did with only one memory access, the multi-level approach requires multiple accesses, which makes it slower.
Modern computer hardware deploys techniques such as automated or semi-automated page table walkers, and caches for the metadata stored in the page table to speed up the access to or the retrieval of the metadata. Unfortunately, software-only applications of the page table data structure cannot use assists like that and need to look for optimizations elsewhere.